package edu.dayu.demo1;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 思路：规律，首先第一个是三个左括号连续，后面依次减少，
 *      这种题型似乎只有递归最好解决。
 *          * 递归的情况 一开始执行 4 次函数，然后第四次被剪枝，留下 （ （（ （（（，然后开始 i =1 的循环
 *          * 然后开始执行 （（（ 这次的，得到((())) 然后返回， （（ 开始继续往下执行。
 */
public class 生成匹配的括号 {
    List<String> res;
    StringBuilder stack;
    int n;
    char[] par;
    int[] count;
    public static void main(String[] args) {
        生成匹配的括号 test = new 生成匹配的括号();
        System.out.println(test.generateParenthesis(3));
    }

    public List<String> generateParenthesis(int n) {
        this.res = new ArrayList<>();
        this.stack = new StringBuilder();
        this.n = n;
        this.par = new char[]{'(', ')'};
        this.count = new int[2];
        brackets();
        return res;
    }

    public void brackets(){
        // 限制左右括号的长度，且包装左括号一直比右边多或相等
        if(count[0] > n || count[1] > count[0]) return; // 合法检查(剪枝)
        // 如果字符串长度 == 2n 就是正确的。
        if(stack.length() == 2 * n){
            res.add(stack.toString());
            return;
        }
        for(int i = 0; i < 2; i++){ // 只有 '('和')'两种可能
            stack.append(par[i]); // 选
            count[i]++;
            brackets();
            stack.deleteCharAt(stack.length() - 1); // 不选
            count[i]--;
        }

    }
}
